import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		long startTime = System.nanoTime();
		Node node;
		BufferedReader br;

		Double latitude, longitude;
		String name;
		int num;
		try {
			/************************/
			br = new BufferedReader(new FileReader("input.txt"));
			ReadFile.setSource(br.readLine());
			ReadFile.setDestination(br.readLine());
			ShortestPath.n = Integer.parseInt(br.readLine());
			/************************/
			ReadFile.fileInput();
			br = new BufferedReader(new FileReader("nodes.txt"));
			while ((name = br.readLine()) != null) {
				num = Integer.parseInt(br.readLine());
				latitude = Double.parseDouble(br.readLine());
				longitude = Double.parseDouble(br.readLine());
				br.readLine();
				node = new Node(num, name, latitude, longitude);
				ShortestPath.hashNode.put(num, node);
				ShortestPath.hashMapOfMappingNumbers.put(name, num);
			}
			//ShortestPath.n = ShortestPath.hashNode.size();
			/* Initializing the matrices */
			ShortestPath
					.setlinkcost(new double[ShortestPath.n][ShortestPath.n]);
			ShortestPath
					.setLinkendcost(new double[ShortestPath.n][ShortestPath.n]);
			ShortestPath.setPrevlink(new int[ShortestPath.n][ShortestPath.n]);
			/***********************************/
			/* Read the edges file */
//			ReadFile.readEdgesFile("edges.txt");
			ShortestPath.createAdjmatrix();
			ShortestPath.turnRestrictedShortestPath(0);

			ShortestPath.arrayList = new ArrayList<Integer>(
					ShortestPath.linkSet);
			Collections.reverse(ShortestPath.arrayList);
			if (ShortestPath.arrayList.get(ShortestPath.arrayList.size() - 1)
					.intValue() != ShortestPath.n - 1) {
				System.out.println("The path does not exist");
			} else
				System.out.println("Path Exists");

			for (int i = 0; i < ShortestPath.arrayList.size(); i++)
				System.out.print(ShortestPath.arrayList.get(i) + " ");
			System.out.println();
			for (int i = 0; i < ShortestPath.arrayList.size(); i++)
				System.out.print(ShortestPath.hashNode.get(
						ShortestPath.arrayList.get(i)).getName()
						+ " ");

			GUI.createGUI();
			long endTime = System.nanoTime();
			System.out.println("\nRunning Time = " + ((endTime - startTime))
					+ " seconds");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
